package com.algorithm.ch1.cjm.other;

/**
 * 位1的个数
 * 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
 * 示例 :
 * <p>
 * 输入: 11
 * 输出: 3
 * 解释: 整数 11 的二进制表示为 00000000000000000000000000001011
 *
 * @Author: Jie Ming Chen
 * @Date: 2018/9/16
 * @Version 1.0
 */
public class HammingWeight {

    public static void main(String[] args) {
        int i = new HammingWeight().hammingWeight(4294967295L);
    }

    public int hammingWeight(long n) {

        int hasOne = isHasOne(n, 0);

        System.out.println(hasOne);

        return hasOne;
    }

    private int isHasOne(long n, int count) {

        if (n == 1) {
            count ++;
            return count;
        } else if (n < 1){
            return count;
        }

        int index = 0;
        long sum = 1;
        while (sum <= n/2) {

            sum = sum * 2;
            index ++;
        }

        if (index != 0) {
            count ++;
        }

        n = n - sum;

        return isHasOne(n, count);
    }
}
